# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        first = None
        prev = None
        t = 0 # 进位

        while l1 or l2:
            cur = ListNode(0)

            if first is None:
                first = cur
            else:
                prev.next = cur

            prev = cur

            cur.val += t # 进位
            if l1:
                cur.val += l1.val
                l1 = l1.next
            if l2:
                cur.val += l2.val
                l2 = l2.next
            t = cur.val // 10
            cur.val = cur.val % 10

        if t:
            prev.next = ListNode(1)

        return first


l1 = ListNode(9)
l1.next = ListNode(9)
l1.next.next = ListNode(9)

l2 = ListNode(1)
# l2.next = ListNode(6)
# l2.next.next = ListNode(4)

l3 = Solution().addTwoNumbers(l1, l2)
print(l3.val, end="")
while l3.next:
    l3 = l3.next
    print(l3.val, end="")





